package caculate.sliding_window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 查找所有串联子串在 s 中的开始索引
 *
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2025-04-08 12:00
 **/
public class FindSubstring {

    public static List<Integer> findSubstring(String s, String[] words) {
        if (s == null || s.isEmpty() || words.length == 0) {
            return new ArrayList<>(0);
        }

        int n = s.length();
        // 字符串长度
        int wordNum = words.length;
        // 步长
        int wordLen = words[0].length();

        List<Integer> list = new ArrayList<>();

        // 初始化基础map
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        // 无论如何都得计算偏移量
        for (int i = 0; i < wordLen; i++) {
            if (i + wordNum * wordLen > n) {
                break;
            }
            Map<String, Integer> cache = new HashMap<>();

            int left = i, right = i;
            while (right + wordLen <= n) {
                String word = s.substring(right, right + wordLen);
                right += wordLen;

                if (!map.containsKey(word)) {
                    cache.clear();
                    left = right;
                } else {
                    cache.put(word, cache.getOrDefault(word, 0) + 1);
                    while (cache.getOrDefault(word, 0) > map.getOrDefault(word, 0)) {
                        String leftWord = s.substring(left, left + wordLen);
                        cache.put(leftWord, cache.get(leftWord) - 1);
                        left+=wordLen;
                    }
                }

                if (right - left == wordLen * wordNum) {
                    list.add(left);
                }
            }
        }

        return list;
    }

    public static List<Integer> findSubstring_1(String s, String[] words) {
        int n = s.length();

        int wordNum = words.length;
        int wordLen = words[0].length();

        List<Integer> res = new ArrayList<>();

        // 偏移量（0， wordLen）
        for (int i = 0; i < wordLen; i++) {
            if (n < wordNum * wordLen + i) {
                break;
            }

            Map<String, Integer> differ = new HashMap<>();
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
            }

            for (int j = 0; j < wordNum; j++) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }

            for (int start = i; start < n - wordLen * wordNum + 1; start+=wordLen) {
                if (start != i) {
                    // 加上最后一个，移除前一个
                    String word = s.substring(start + wordLen * (wordNum - 1), start + wordLen * wordNum);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }

                    // 移除前一个
                    word = s.substring(start - wordLen, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }
                // 如果为空标识符合条件
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        String s = "aaaaaaaaaaaaaa";
        String[] words = {"aa","aa"};
        System.out.println(findSubstring(s, words));
    }

}
